package test.day04;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Permutations {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();
	public List<List<Integer>> permute(int[] nums) {
		if (nums.length == 0) {
			return result;
		}
		backtrack(nums, path);
		return result;
	}
	public void backtrack(int[] nums, LinkedList<Integer> path) {
		if (path.size() == nums.length) {
			result.add(new ArrayList<>(path));
		}
		for (int i = 0; i < nums.length; i++) {
			// 如果path中已有，则跳过
			if (path.contains(nums[i])) {
				continue;
			}
			path.add(nums[i]);
			backtrack(nums, path);
			path.removeLast();
		}
	}

	List<List<Integer>> list = new ArrayList<>();
	public List<List<Integer>> subsets(int[] nums) {
		if(nums.length == 0){
			return null;
		}
		List<Integer> temp = new ArrayList<>();
		backTrace(0, nums, temp);
		return list;
	}

	public void backTrace(int start, int[] nums, List<Integer> temp){
		list.add(new ArrayList<>(temp));
		//从start开始遍历，避免重复
		for(int j = start; j < nums.length; j++){
			temp.add(nums[j]);
			backTrace(j+1,nums,temp);
			temp.remove(temp.size()-1);
		}
	}

	public static void main(String[] args) {
		Permutations permutations = new Permutations();
		int[] nums = new int[]{1,2,3};
		permutations.permute(nums);
	}
}
